/*
The pseudo code can be found in page 31
*/

#include <iostream>
using namespace std;

int A[5]={5,4,3,2,1};
const int maxInt = 2147483647;

void merge(int *array, int p, int q, int r)
{
//	cout << "p="<<p<<" "<<"q="<<q<<" "<<"r="<<r<<endl;
	int len1 = q-p+1;	// Attention
	int len2 = r-q;		// Attention
// copy two subarray
	int *subarray1 = new int[len1 + 1];
	int *subarray2 = new int[len2 + 1];
	int i,j;
	for(i=0;i<len1;i++)
	{
		subarray1[i] = A[p+i];	// Attention
	}
	for(j=0;j<len2;j++)
	{
		subarray2[j] = A[q+j+1];	//Attention
	}

	subarray1[len1] = maxInt;
	subarray2[len2] = maxInt;
//	cout << subarray1[0] << " " << subarray1[1] << " " << subarray2[0] << " " << subarray2[1]<<endl;
// merge
	int k;
	i=0,j=0;
	for(k=p; k<=r; k++)	// Attention
	{
		if(subarray1[i] < subarray2[j])
		{
			A[k] = subarray1[i];
			i++;
		}
		else
		{
			A[k] = subarray2[j];
			j++;
		}
	} 

/*	int m=0;
	for(m=0;m<5;m++)	
	  cout << A[m] << " ";
	cout << endl;	
*/	return;	
}

void merge_sort(int *array, int p, int r)
{
	if(p<r)
	{
		int q=(p+r)/2;
//		cout << "p=" <<p <<" " << "q=" << q << " " << "r=" << r << endl;
        merge_sort(A,p,q);
		merge_sort(A,q+1,r);
		merge(A,p,q,r);
	}
	return;
}

int main()
{
	merge_sort(A,0,4);	// Attention
	int i;
	for(i=0;i<5;i++)
	{
		cout << A[i] << " ";
	}
	cout << endl;
	return 0;	
}
